Search for: All records

Recently, there has been much progress in understanding stationary measures for colored (also called multi-species or multi-type) interacting particle systems, motivated by asymptotic phenomena and rich underlying algebraic and combinatorial structures (such as nonsymmetric Macdonald polynomials). In this paper, we present a unified approach to constructing stationary measures for most of the known colored particle systems on the ring and the line, including (1) the Asymmetric Simple Exclusion Process (multispecies ASEP, or mASEP); (2) the q-deformed Totally Asymmetric Zero Range Process (TAZRP) also known as the q-Boson particle system; (3) the q-deformed Pushing Totally Asymmetric Simple Exclusion Process (q-PushTASEP). Our method is based on integrable stochastic vertex models and the Yang-Baxter equation. We express the stationary measures as partition functions of new "queue vertex models" on the cylinder. The stationarity property is a direct consequence of the Yang-Baxter equation. For the mASEP on the ring, a particular case of our vertex model is equivalent to the multiline queues of Martin (arXiv:1810.10650). For the colored q-Boson process and the q-PushTASEP on the ring, we recover and generalize known stationary measures constructed using multiline queues or other methods by Ayyer-Mandelshtam-Martin (arXiv:2011.06117, arXiv:2209.09859), and Bukh-Cox (arXiv:1912.03510). Our proofs of stationarity use the Yang-Baxter equation and bypass the Matrix Product Ansatz used for the mASEP by Prolhac-Evans-Mallick (arXiv:0812.3293). On the line and in a quadrant, we use the Yang-Baxter equation to establish a general colored Burke's theorem, which implies that suitable specializations of our queue vertex models produce stationary measures for particle systems on the line. We also compute the colored particle currents in stationarity. 

Polynomial approximations for e−x and ex have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for n sample points in Θ(logn) dimensions with error δ=n−Θ(1). We show that the running time one can achieve depends on the square of the diameter of the point set, B, with a transition at B=Θ(logn) mirroring the corresponding transition in dB;δ(e−x): - When B=o(logn), we give the first algorithm running in time n1+o(1). - When B=κlogn for a small constant κ>0, we give an algorithm running in time n1+O(loglogκ−1/logκ−1). The loglogκ−1/logκ−1 term in the exponent comes from analyzing the behavior of the leading constant in our computation of dB;δ(e−x). - When B=ω(logn), we show that time n2−o(1) is necessary assuming SETH. 

Abstract We introduce and study a one parameter deformation of the polynuclear growth (PNG) in (1+1)-dimensions, which we call the $$t$$-PNG model. It is defined by requiring that, when two expanding islands merge, with probability $$t$$ they sprout another island on top of the merging location. At $t=0$, this becomes the standard (non-deformed) PNG model that, in the droplet geometry, can be reformulated through longest increasing subsequences of uniformly random permutations or through an algorithm known as patience sorting. In terms of the latter, the $$t$$-PNG model allows errors to occur in the sorting algorithm with probability $$t$$. We prove that the $$t$$-PNG model exhibits one-point Tracy–Widom Gaussian Unitary Ensemble asymptotics at large times for any fixed $$t\in [0,1)$$, and one-point convergence to the narrow wedge solution of the Kardar–Parisi–Zhang equation as $$t$$ tends to $$1$$. We further construct distributions for an external source that are likely to induce Baik–Ben Arous–Péché-type phase transitions. The proofs are based on solvable stochastic vertex models and their connection to the determinantal point processes arising from Schur measures on partitions.